<?php

/**
 * 树
 *
 * 0是根结点
 */
class Newtree
{

    public $data = array();
    private $child = array(-1 => array());
    private $layer = array(0 => 0);
    private $parent = array();
    private $value_field = '';

    /**
     * 生成树型结构所需修饰符号，可以换成图片
     * @var array
     */
    public $icon = array('│', '├', '└');
    public $nbsp = "&nbsp;";

    /**
     * @access private
     */
    public $ret = '';
    public static $instances = array();

    public static function instance($type = 'defaule')
    {
      
        if (!isset(Newtree::$instances[$type]))
        {
            $class = __CLASS__;
            Newtree::$instances[$type] = new $class();
        }
         
        return Newtree::$instances[$type];
    }

    /**
     * 构造函数
     *
     * @param mix $value
     */
    function construct($value = 'root')
    {
        $this->Newtree($value);
    }

    function Newtree()
    {
        //$this->setNode(0, -1, $value);
    }

    /**
     * 构造树
     *
     * @param array $nodes 结点数组
     * @param string $id_field
     * @param string $parent_field
     * @param string $value_field
     */
    function setTree($nodes, $id_field, $parent_field, $value_field)
    {
       // unset($this->data);
        $this->value_field = $value_field;
        foreach ($nodes as $node)
        {
            $this->setNode($node[$id_field], $node[$parent_field], $node);
        }
        $this->setLayer();
    }

    /**
     * 得到子级数组
     * @param int
     * @return array
     */
    public function get_child_arr($myid)
    {
        $a = $newarr = array();
        if (is_array($this->data))
        {
            foreach ($this->data as $id => $a)
            {
                if ($a['parent_id'] == $myid)
                    $newarr[$id] = $a;
            }
        }
        return $newarr ? $newarr : false;
    }

    /**
     * 得到树型结构
     * @param int ID，表示获得这个ID下的所有子级
     * @param string 生成树型结构的基本代码，例如："<option value=\$id \$selected>\$spacer\$name</option>"
     * @param int 被选中的ID，比如在做树型下拉框的时候需要用到
     * @return string
     */
    public function get_tree($myid, $sid = 0, $str = "<option value = \$id \$selected>\$spacer\$name</option>", $selected_str = 'selected', $adds = '', $str_group = '')
    {
        $number = 1;
        $child = $this->get_child_arr($myid);

        if (is_array($child))
        {
            $total = count($child);
            foreach ($child as $id => $value)
            {
                $j = $k = '';
                if ($number == $total)
                {
                    $j .= $this->icon[2];
                }
                else
                {
                    $j .= $this->icon[1];
                    $k = $adds ? $this->icon[0] : '';
                }
                $spacer = $adds ? $adds . $j : '';
                if (Arr::validate_arr($sid))
                {
                    $selected = in_array($id, $sid) ? $selected_str : '';
                }
                else
                {
                    $selected = $id == $sid ? $selected_str : '';
                }
                @extract($value);
                $parent_id == 0 && $str_group ? eval("\$nstr = \"$str_group\";") : eval("\$nstr = \"$str\";");
                $this->ret .= $nstr;
                $nbsp = $this->nbsp;
                $this->get_tree($id, $sid, $str, $selected_str, $adds . $k . $nbsp, $str_group);
                $number++;
            }
        }
        return $this->ret;
    }

    /**
     * 取得options
     *
     * @param int $layer
     * @param int $root
     * @param string $space
     * @return array (id=>value)
     */
    function getOptions($layer = 0, $root = 0, $except = NULL, $space = '&nbsp;&nbsp;')
    {
        $options = array();
        $childs = $this->getChilds($root, $except);
        foreach ($childs as $id)
        {
            if ($id > 0 && ($layer <= 0 || $this->getLayer($id) <= $layer))
            {
                $options[$id] = $this->getLayer($id, $space) . htmlspecialchars($this->getValue($id));
            }
        }
        return $options;
    }

    /**
     * 设置结点
     *
     * @param mix $id
     * @param mix $parent
     * @param mix $value
     */
    function setNode($id, $parent, $value)
    {
        $parent = $parent ? $parent : 0;

        $this->data[$id] = $value;
        if (!isset($this->child[$id]))
        {
            $this->child[$id] = array();
        }

        if (isset($this->child[$parent]))
        {
            $this->child[$parent][] = $id;
        }
        else
        {
            $this->child[$parent] = array($id);
        }

        $this->parent[$id] = $parent;
    }

    /**
     * 计算layer
     */
    function setLayer($root = 0)
    {
        foreach ($this->child[$root] as $id)
        {
            $this->layer[$id] = $this->layer[$this->parent[$id]] + 1;
            if ($this->child[$id])
                $this->setLayer($id);
        }
    }

    /**
     * 先根遍历，不包括root
     *
     * @param array $tree
     * @param mix $root
     * @param mix $except 除外的结点，用于编辑结点时，上级不能选择自身及子结点
     */
    function getList(&$tree, $root = 0, $except = NULL)
    {
        foreach ($this->child[$root] as $id)
        {
            if ($id == $except)
            {
                continue;
            }

            $tree[] = $id;

            if ($this->child[$id])
                $this->getList($tree, $id, $except);
        }
    }

    function getValue($id)
    {
        return $this->data[$id][$this->value_field];
    }

    function getLayer($id, $space = false)
    {
        return $space ? str_repeat($space, $this->layer[$id]) : $this->layer[$id];
    }

    function getParent($id)
    {
        return $this->parent[$id];
    }

    /**
     * 取得祖先，不包括自身
     *
     * @param mix $id
     * @return array
     */
    function getParents($id)
    {
        while ($this->parent[$id] != -1)
        {
            $id = $parent[$this->layer[$id]] = $this->parent[$id];
        }

        ksort($parent);
        reset($parent);

        return $parent;
    }

    function getChild($id)
    {
        return $this->child[$id];
    }

    /**
     * 取得子孙，先根遍历
     *
     * @param int $id
     * @return array
     */
    function getChilds($id = 0, $except = NULL)
    {
        $child = array($id);
        $this->getList($child, $id, $except);
        unset($child[0]);

        return $child;
    }

    /**
     * 先根遍历，数组格式
     * array(
     *     array('id' => '', 'value' => '', children => array(
     *         array('id' => '', 'value' => '', children => array()),
     *     ))
     * )
     */
    function getArrayList($root = 0, $layer = NULL)
    {
        $data = array();
        foreach ($this->child[$root] as $id)
        {
            if ($layer && $this->layer[$this->parent[$id]] > $layer - 1)
            {
                continue;
            }
            $data[$id] = array('id' => $id, 'value' => $this->getValue($id), 'children' => $this->child[$id] ? $this->getArrayList($id, $layer) : array());
        }
        return $data;
    }

    /**
     * 得到当前位置数组
     * @param int
     * @return array
     */
    public function get_pos($myid, &$newarr = array())
    {
        $a = array();
        if (!isset($this->data[$myid]))
            return false;
        $newarr[] = $this->data[$myid];
        $pid = $this->data[$myid]['parent_id'];
        if (isset($this->data[$pid]))
        {
            $this->get_pos($pid, $newarr);
        }
        if (is_array($newarr))
        {
            krsort($newarr);
            foreach ($newarr as $v)
            {
                $a[$v['id']] = $v;
            }
        }
        return $a;
    }

    public static function delete()
    {
        Newtree::$instances = array();
    }

}

?>